home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / c_math.arc / QSORT.C < prev    next >
Text File  |  1983-07-02  |  3KB  |  126 lines
  1.  
  2. /* @(#)qsort.c  4.1 (Berkeley) 12/21/80 */
  3.  
  4. static int      (*qscmp)();
  5. static int      qses;
  6.  
  7. qsort(a, n, es, fc)
  8. char *a;
  9. unsigned n;
  10. int es;
  11. int (*fc)();
  12. {
  13.         qscmp = fc;
  14.         qses = es;
  15.         qs1(a, a+n*es);
  16. }
  17.  
  18. static qs1(a, l)
  19. char *a, *l;
  20. {
  21.         register char *i, *j;
  22.         register es;
  23.         char **k;
  24.         char *lp, *hp;
  25.         int c;
  26.         unsigned n;
  27.  
  28.  
  29.         es = qses;
  30.  
  31. start:
  32.         if((n=l-a) <= es)
  33.                 return;
  34.         n = es * (n / (2*es));
  35.         hp = lp = a+n;
  36.         i = a;
  37.         j = l-es;
  38.         for(;;) {
  39.                 if(i < lp) {
  40.                         if((c = (*qscmp)(i, lp)) == 0) {
  41.                                 qsexc(i, lp -= es);
  42.                                 continue;
  43.                         }
  44.                         if(c < 0) {
  45.                                 i += es;
  46.                                 continue;
  47.                         }
  48.                 }
  49.  
  50. loop:
  51.                 if(j > hp) {
  52.                         if((c = (*qscmp)(hp, j)) == 0) {
  53.                                 qsexc(hp += es, j);
  54.                                 goto loop;
  55.                         }
  56.                         if(c > 0) {
  57.                                 if(i == lp) {
  58.                                         qstexc(i, hp += es, j);
  59.                                         i = lp += es;
  60.                                         goto loop;
  61.                                 }
  62.                                 qsexc(i, j);
  63.                                 j -= es;
  64.                                 i += es;
  65.                                 continue;
  66.                         }
  67.                         j -= es;
  68.                         goto loop;
  69.                 }
  70.  
  71.  
  72.                 if(i == lp) {
  73.                         if(lp-a >= l-hp) {
  74.                                 qs1(hp+es, l);
  75.                                 l = lp;
  76.                         } else {
  77.                                 qs1(a, lp);
  78.                                 a = hp+es;
  79.                         }
  80.                         goto start;
  81.                 }
  82.  
  83.  
  84.                 qstexc(j, lp -= es, i);
  85.                 j = hp -= es;
  86.         }
  87. }
  88.  
  89. static qsexc(i, j)
  90. char *i, *j;
  91. {
  92.         register char *ri, *rj, c;
  93.         int n;
  94.  
  95.         n = qses;
  96.         ri = i;
  97.         rj = j;
  98.         do {
  99.                 c = *ri;
  100.                 *ri++ = *rj;
  101.                 *rj++ = c;
  102.         } while(--n);
  103. }
  104.  
  105. static qstexc(i, j, k)
  106. char *i, *j, *k;
  107. {
  108.         register char *ri, *rj, *rk;
  109.         int c;
  110.         int n;
  111.  
  112.         n = qses;
  113.         ri = i;
  114.         rj = j;
  115.         rk = k;
  116.         do {
  117.                 c = *ri;
  118.                 *ri++ = *rk;
  119.                 *rk++ = *rj;
  120.                 *rj++ = c;
  121.         } while(--n);
  122. }
  123. 107% = *ri;
  124.                 *ri++ = *rk;
  125.                 *rk++ = *rj;
  126.